// 第 N 个神奇数字
// 测试链接 : https://leetcode.cn/problems/nth-magical-number/
public class NthMagicalNumber {
    public int nthMagicalNumber(int n, int a, int b) {
        long lcm = (int)lcm(a,b);

        long l = 1;
        long r = (long)n * Math.min(a,b) ;
        long ans = 0;

        while(l <= r){
            long mid = (l + r) / 2;

            //1...mid 之间神奇的数的个数
            if(mid / a + mid / b - mid / lcm  >= n){
                ans = mid;
                r = mid - 1;
            }else {
                l = mid + 1;
            }
        }

        return (int)(ans % 1000000007) ;
    }

    public long gcd(long a, long b){
        return b == 0 ? a : gcd(b, a%b);
    }

    public long lcm(long a, long b){
        return (long)a / gcd(a,b) * b;
    }
}
